package inner_sort

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/6/25 23:54
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 快速排序-双向快排
 * */
type QuickSortDuplex struct {
	FromHighToLow bool // true表示从高到低排序,默认 false 表示从低到高排序
}

func NewQuickSortDuplex(options ...C.Options) *BucketSort {
	opt := C.NewOptions(options...)
	return &BucketSort{
		FromHighToLow: opt.FromHighToLow,
	}
}

func (m *QuickSortDuplex) SortMethod(array []int) {
	if len(array) < 2 {
		return
	}
	m.sort(array, 0, len(array)-1)
}

func (m *QuickSortDuplex) sort(array []int, left, right int) {
	if left >= right {
		return
	}
	flag, l, r := array[left], left, right
	for l < r {
		/*tips ：下方的两个循环必须有=，用于处理数组中有相同数字的情况，不然指针无法前进，导致死循环
		tips 2: 因为退出循环需要交换指针，为了保证 l和r指针 相遇时候是在不小于标记元素(array[left])的左边而不是右边，
		"="号条件必须写成 array[r] >= 标记元素(array[left]),
		比如在数组[2,1,1,2,2,3,3],标记元素是2，那么l和r应该相遇在 index=3的位置，而不是index=5的位置
		tips 3: 因为 l指针容易前进一步，导致循环外的交换不正确，所以需要将 右指针移动的for循环写在 左指针移动的for循环前面
				或者通过是否有 = 来控制 */
		for l < r && array[r] >= flag {
			r--
		}
		for l < r && array[l] <= flag {
			l++
		}
		if l < r {
			array[l], array[r] = array[r], array[l]
		}
	}
	array[left], array[l] = array[l], array[left]
	m.sort(array, left, l-1)
	m.sort(array, l+1, right)
}

func (m *QuickSortDuplex) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.Sort},
		Desc: &C.Desc{
			Name:   "QuickSortDuplex",
			NameCn: "内部排序:快速排序:双向快排",
			ParamsDesc: map[string]string{
				"fromHighToLow": "true表示从高到低排序, 默认 false 表示从低到高排序",
			},
			Example: map[int]string{
				1: "输入[1,3,2],跳用SortMethod方法进行排序后，输出[1,2,3]",
			},
		},
	}
}